#include "sokoban.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <time.h>
#include "main.h"
#include "util/algorithm.h"

void room_sokoban_layout (Segment* segment, Layout* layout, Generator* generator)
{
	int width = 12;
	int height = 12;
	int root[MAX_ROOTS];
	int n_roots = 0;
	
	for (int i = 0; i < segment->n_roots; i++)
	{
		assert(segment->root[i]->n_rooms > 0);
		root[n_roots++] = segment->root[i]->room[0];
	}
	
	segment->room[0] = generator->gen_room (layout, width, height, root, n_roots);
	segment->n_rooms = 1;
}

void room_sokoban_content (Segment* segment, Layout* layout, Map* map,
                           Coord* entrance, int n_entrances,
                           Coord* exit, int n_exits)
{
	assert(segment->n_rooms == 1); // other values not supported
	
	int room_id = segment->room[0];
	assert((room_id >= 0) && (room_id < layout->n_rooms));
	
#if TOWERHACK_DEBUG_OBJECTS
	Rect* room = &layout->room[room_id].area;
	Coord cbox1 = { room->left+3, room->top+3, room->z };
	Coord cbox2 = { room->left+5, room->top+4, room->z };
	Coord cbox3 = { room->left+3, room->top+5, room->z };
	
	MapObject* box1 = map_add_object (map, cbox1);
	MapObject* box2 = map_add_object (map, cbox2);
	MapObject* box3 = map_add_object (map, cbox3);
	
	map_object_make_sokobox (box1);
	map_object_make_sokobox (box2);
	map_object_make_sokobox (box3);
#else
	segment_plant_obstacles (map, exit, n_exits);
#endif

	// TODO: use implementation below for real room content, not placeholders
}

// SOKOBAN GENERATOR V1 IMPL BELOW

#define SOKOBAN_ROOM_MAX_WH 25
#define SOKOGEN_ITERATIONS 10
#define SOKOGEN_PULLSTEPS (3 + rand() % 6)
#define SOKOBAN_MAX_BOXES 8

enum {
	WALL,
	FLOOR,
	GOAL,
	BOX,
	GOAL_BOX
};

static void dig_along_path (int width, int height, int (*field)[width][height], Coord* path, int length);

// Generates a sokoban puzzle to fit the specified room
void gen_sokoban (int width, int height, int (*field)[width][height],
                  Coord entrances[], int n_entrances,
                  Coord exits[], int n_exits)
{
	for (int y = 1; y < height-1; y++)
	for (int x = 1; x < width-1; x++) {
		(*field)[x][y] = WALL;
	}

	Coord cursor;
	cursor.x = rand() % (width-6) + 3;
	cursor.y = rand() % (height-6) + 3;
	cursor.z = 0;

	AstarResult result;
	Space space = { 0, width, 0, height, 0, 1 }; // for A* and flood search

	Coord boxes[SOKOBAN_MAX_BOXES];
	int n_boxes = 0;

	Coord wall_coords;

	int has_box (Coord c)
	{
		if (((*field)[c.x][c.y] == BOX) ||
		    ((*field)[c.x][c.y] == GOAL_BOX))
		{
			return 1;
		} else {
			return 0;
		}
	}

	void set_box (Coord c)
	{
		if (((*field)[c.x][c.y] == FLOOR) || ((*field)[c.x][c.y] == WALL)) {
			(*field)[c.x][c.y] = BOX;
		} else
		if ((*field)[c.x][c.y] == GOAL) {
			(*field)[c.x][c.y] = GOAL_BOX;
		} else {
			assert(0);
		}
	}

	void unset_box (Coord c)
	{
		if ((*field)[c.x][c.y] == BOX) {
			(*field)[c.x][c.y] = FLOOR;
		} else
		if ((*field)[c.x][c.y] == GOAL_BOX) {
			(*field)[c.x][c.y] = GOAL;
		} else {
			assert(0);
		}
	}

	void wall_to_goalbox (Coord c)
	{
		assert((*field)[c.x][c.y] == WALL);
		(*field)[c.x][c.y] = GOAL_BOX;
	}

	bool is_wall (Coord c)
	{
		if ((*field)[c.x][c.y] == WALL) {
			wall_coords = c;
			return true;
		} else {
			return false;
		}
	}

	bool can_go (Coord c1, Coord c2)
	{
		if ((c2.x <= 0) || (c2.y <= 0) || (c2.x >= width-1)  || (c2.y >= height-1)) {
			return 0; // out of bounds
		} else
		if (has_box(c2)) {
			return 0; // obstructed by a box
		} else {
			return 1;
		}
	}

	int cost_step (Coord pprev, Coord prev, Coord next)
	{
		assert(next.x > 0);
		assert(next.x < width-1);
		assert(next.y > 0);
		assert(next.y < height-1);
		assert(!has_box(next));

		int tile = (*field)[next.x][next.y];
		if (tile == WALL) {
			return 100;
		} else
		if ((tile == FLOOR) || (tile == GOAL)) {
			return 1;
		} else {
			assert(0);
		}
	}

	int pull_step (Coord boxc)
	{
		Coord nextcur = {
			cursor.x + (cursor.x - boxc.x),
			cursor.y + (cursor.y - boxc.y),
			cursor.z
		};
		if (can_go(cursor, nextcur)) {
			unset_box (boxc);
			set_box (cursor);
			cursor = nextcur;
			return 1;
		} else {
			return 0;
		}
	}

	Coord random_neighbour (Coord c)
	{
		int second_try = 0;

		switch (rand() % 4) {

		case 0: more:
			if ((c.x > 2) && !has_box ( (Coord) { c.x-1, c.y, c.z } )) {
				c.x--;
				break;
			} else {} // fall through case

		case 1:
			if ((c.y > 2) && !has_box ( (Coord) {c.x, c.y-1, c.z} )) {
				c.y--;
				break;
			} else {} // fall through case

		case 2:
			if ((c.x < width-3) && !has_box ( (Coord) {c.x+1, c.y, c.z} )) {
				c.x++;
				break;
			} else {} // fall through case

		case 3:
			if ((c.y < height-3) && !has_box ( (Coord) {c.x, c.y+1, c.z} )) {
				c.y++;
				break;
			} else {
				assert(!second_try);
				second_try = 1;
				goto more;
			}
		}

		return c;
	}

	void pull_existing_box (Coord* boxc)
	{
		Coord next_to_box = random_neighbour (*boxc);
		astar_search(next_to_box, cursor, space, &result, &can_go, &cost_step, NULL, NULL);
		assert(result.found);
		dig_along_path (width, height, field, result.path, result.length);
		cursor = result.path[0];
		for (int i = 0; i < SOKOGEN_PULLSTEPS; i++) {
			Coord c = cursor;
			if (! pull_step (*boxc)) break; // we hit an obstacle
			*boxc = c;
		}
	}

	int make_new_box ()
	{
		bool found = flood_search(cursor, space, 1, 1, &can_go, &is_wall);
		assert(found);
		wall_to_goalbox(wall_coords);

		int box_id = n_boxes++;
		boxes[box_id] = wall_coords;
		return box_id;
	}

	for (int i = 0; i < n_exits; i++) {
		astar_search(exits[i], cursor, space, &result, &can_go, &cost_step, NULL, NULL);
		assert(result.found);
		dig_along_path (width, height, field, result.path, result.length);
	}

	make_new_box ();
	for (int i = 0; i < SOKOGEN_ITERATIONS; i++) {
		if ((n_boxes < SOKOBAN_MAX_BOXES) && (rand() % 10) < 3) {
			int box_id = make_new_box ();
			pull_existing_box (&boxes[box_id]);
		} else {
			pull_existing_box (&boxes[rand() % n_boxes]);
		}
	}

	for (int i = 0; i < n_entrances; i++) {
		astar_search(entrances[i], cursor, space, &result, &can_go, &cost_step, NULL, NULL);
		assert(result.found);
		dig_along_path (width, height, field, result.path, result.length);
	}
}

static void dig_along_path (int width, int height, int (*field)[width][height], Coord* path, int length)
{
	for(int i = 0; i < length; i++) {
		if ((*field)[path->x][path->y] == WALL) {
			(*field)[path->x][path->y] = FLOOR;
		}
		path++;
	}
}

#ifdef TEST_SOKOBAN

static void print_field (int width, int height, int (*field)[width][height])
{
	for (int y = 0; y < height; y++) {
		for (int x = 0; x < width; x++) {
			printf("%c", "X.Go*"[(*field)[x][y]]);
		}
		printf("\n");
	}
}

static void test_gen_sokoban (char* fieldstr, int w, int h)
{
	assert(strlen(fieldstr) == (w * h));
	int field[w][h];
	Coord entrances[w*h];
	int n_entrances = 0;
	Coord exits[w*h];
	int n_exits = 0;

	for (int y = 0; y < h; y++)
	for (int x = 0; x < w; x++) {
		if (fieldstr[y*w+x] == 'E') {
			entrances[n_entrances++] = (Coord) { x, y, 0 };
			field[x][y] = FLOOR;
		} else
		if (fieldstr[y*w+x] == 'X') {
			exits[n_exits++] = (Coord) { x, y, 0 };
			field[x][y] = FLOOR;
		} else {
			field[x][y] = WALL;
		}
	}

	gen_sokoban (w, h, &field, entrances, n_entrances, exits, n_exits);
	print_field (w, h, &field);
}

int main ()
{
	srand(time(NULL));
	algorithm_init (1000000);

	test_gen_sokoban ("############"
	                  "#          X"
	                  "E          #"
	                  "#          #"
	                  "E          X"
	                  "#          #"
	                  "############", 12, 7);
	return 0;
}

#endif
